package xyz.scootaloo.oj.iq

import org.junit.Test
import xyz.scootaloo.oj.ds.ListNode
import xyz.scootaloo.oj.ds.helper.CollectionBuilder

/**
 * @author flutterdash@qq.com
 * @since 2021/4/17 9:41
 */
class M0202 {

    private fun kthToLast(head: ListNode?, k: Int): Int {
        if (head == null) return -1
        if (head.next == null) return head.`val`

        var slow = head
        var fast = head
        var count = 1
        var slowCount = 1

        while (fast?.next != null) {
            if (fast.next?.next == null) {
                fast = fast.next
                count++
            } else {
                fast = fast.next.next
                count += 2
            }
            slow = slow?.next
            slowCount++
        }
        val target = count - k + 1
        if (target == 1)
            return head.`val`
        return if (target > slowCount) {
            for (pos in slowCount until target) {
                slow = slow?.next
            }
            slow?.`val` ?: -1
        } else {
            slow = head
            for (pos in 1 until target) {
                slow = slow?.next
            }
            slow?.`val` ?: -1
        }
    }

    @Test
    fun test0() {
        val value = kthToLast(CollectionBuilder.initNode(1, 2), 2)
        println(value)
    }

}
